package com.test.ita;

import org.apache.commons.collections.CollectionUtils;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

/**
 * Created by IntelliJ IDEA.
 * User: gpss
 * Date: 7/12/11
 * Time: 6:01 PM
 * To change this template use File | Settings | File Templates.
 */
public class RebusFinder {
    private HashSet<String> findUniquePictureSet (String word) {
        char[] combChar = word.toCharArray();
        HashSet<String> unionSet = new HashSet<String>();
        long st = System.currentTimeMillis();
        for (Character c : combChar) {
            HashSet<String> charPicSet = Utils.dictionary.get((Character)c);
            unionSet.addAll(charPicSet);
        }
        return unionSet;
    }
    private HashSet<String> findAllUniquePictures (String word) {
        char[] combChar = word.toCharArray();
        HashSet<String> unionSet = new HashSet<String>();
        long st = System.currentTimeMillis();
        if (combChar.length == 1) {
            return Utils.dictionary.get((Character)combChar[0]);
        } else if(combChar.length > 1){
         ArrayList<String> unionresult = (ArrayList<String>) CollectionUtils.union(Utils.dictionary.get((Character)combChar[0])
                ,findPictureWords(word.substring(1)));
         for(Iterator it = unionresult.iterator();it.hasNext();) {
             // cost per picture - change the object<String,cost>
             String picture = (String) it.next();
             unionSet.add(picture);
//             if (Utils.findCombinationInOrder(combination,picture)) {
//                unionSet.add(picture);
//             }

         }

        }
        long et = System.currentTimeMillis();
//        System.out.println("Time taken to complete findPicturewords one iteration : "+(et-st));
        return unionSet;

    }

    private HashSet<String> findPictureWords(String combination) {
        char[] combChar = combination.toCharArray();
        HashSet<String> unionSet = new HashSet<String>();
        long st = System.currentTimeMillis();
        if (combChar.length == 1) {
            return Utils.dictionary.get((Character)combChar[0]);
        } else if(combChar.length > 1){
         ArrayList<String> unionresult = (ArrayList<String>) CollectionUtils.intersection(Utils.dictionary.get((Character)combChar[0])
                ,findPictureWords(combination.substring(1)));
         for(Iterator it = unionresult.iterator();it.hasNext();) {
             // cost per picture - change the object<String,cost>
             String picture = (String) it.next();
             unionSet.add(picture);
//             if (Utils.findCombinationInOrder(combination,picture)) {
//                unionSet.add(picture);
//             }

         }

        }
        long et = System.currentTimeMillis();
//        System.out.println("Time taken to complete findPicturewords one iteration : "+(et-st));
        return unionSet;
    }



    private RebusNode findBestRebusPicture(String word,String comb, HashSet<String> picSet) {
//        int cost = 0;
//        String minCostPic = "";
        long st = System.currentTimeMillis();
        RebusNode rn = null;
        for(Iterator it = picSet.iterator();it.hasNext();) {
            String pic = (String) it.next();
            LCSCell[][] lcsTable = Utils.computeLCS(word,pic);
            String lcs = Utils.printLCS(lcsTable,word,word.length(),pic.length()).reverse().toString();
            //System.out.println("Word : "+word+" LCS : "+lcs+" Picture : "+pic);
            if(rn == null) {

                rn = Utils.getRebusNode(word,lcs,pic);
            }
            RebusNode nextRn = Utils.getRebusNode(word,lcs, pic);
//            System.out.println(" next rn : "+nextRn.getRebus()+ " picture : "+pic);
            if (nextRn.getLeft().getRebus() == null || "".equalsIgnoreCase(nextRn.getLeft().getRebus())) {
                System.out.println(" Left nothing : Right residue : "+nextRn.getRight().getRebus());
            }
            if(nextRn.getCost() <= rn.getCost()) { //nextRn.getCost() <= rn.getCost()
                System.out.println("Rebus that got picked up : "+nextRn.getRebus() + " LCS : "+lcs+" Add: "+nextRn.getLeft().getRebus()+" sub: "+nextRn.getRight().getRebus());
                rn = nextRn;
            }
        }
//        System.out.println("Combination : "+comb+" Picture : "+minCostPic+" cost : "+cost);
        long et = System.currentTimeMillis();
//        System.out.println("Time taken to complete findBestRebusPicture : "+(et-st));
        return rn;
    }


    public RebusNode rebusGenAlgorithm(String word) {
        if (word == null || word.length() <= 0) return new RebusNode("",-1,null,null);

        ArrayList<CombinationBean> combList = new ArrayList<CombinationBean>();

        HashSet<String> picSet = null;
        picSet = findUniquePictureSet(word);
//        //Todo refine this logic little bit - feels shaky
        if(word.length() == 1 || picSet == null || picSet.size() < 1) {
            picSet = findUniquePictureSet(word);
        }

        RebusNode rn = findBestRebusPicture(word,"",picSet);

        if (rn != null) {
            if (rn.getLeft() != null && rn.getLeft().getRebus() != null && rn.getLeft().getRebus().length() > 0) {
                System.out.println("Left : "+rn.getLeft().getRebus());
                System.out.println("Recursion starts here");

                rn.setLeft(rebusGenAlgorithm(rn.getLeft().getRebus()));
                if (rn.getRight() != null && rn.getRight().getRebus() != null
                        && !"".equalsIgnoreCase(rn.getRight().getRebus()))
                rn.setRight(new RebusNode(rn.getRight().getRebus()+rn.getLeft().getRight().getRebus(),0,null,null));
            }

        }

        return rn;
    }

    public static void main(String[] args)  {
        RebusFinder rf = new RebusFinder();
        RebusNode rn = rf.rebusGenAlgorithm("sl");   //'sl'  -> :castle+-cate
//        System.out.println("Rebus : "+rn.getRebus());
        Utils.printRebus("",rn,"");

    }


/*
    public RebusNode rebusGen(String word) {

         RebusNode theBestRebus = null;
         HashMap<Integer,ArrayList<RebusNode>> bestRebusMap = new HashMap<Integer, ArrayList<RebusNode>>();
         long st = System.currentTimeMillis();
         boolean skipSingleChar = false;
         // This is for word length > 1
         for (int i=word.length()-1;i>0;i--) {
             for(Iterator it = Utils.findCombinations(word, i).iterator();it.hasNext();) {
                      String combStr = (String) it.next();
                    //System.out.println("Combination : "+ combStr);
                 long stp = System.currentTimeMillis();

                 HashSet<String> picSet = (HashSet<String>) findPictureWords(combStr);
                 if (combStr.length() > 1 && picSet.size() > 0) {
                     skipSingleChar = true;
                 }
//                System.out.println("Time taken to complete findPicturewords all  iteration for combination : "+
//                        combStr+" : "+(System.currentTimeMillis()-stp));
                 if (combStr.length() > 1 || !skipSingleChar) {
                     RebusNode rn = findBestRebusPicture(word,combStr,picSet);
                         if (rn != null) {
                             System.out.println("Right : "+rn.getRight().getRebus());
                             if (theBestRebus == null) {
                                 theBestRebus = rn;
                             } else if (rn.getCost() <= theBestRebus.getCost() ) {
                                 theBestRebus = rn;
                             }

                         }

                 }
                }


         }

         if (word.length() == 1) {
             theBestRebus = findBestRebusPicture(word,word,findPictureWords(word));
         }

         long et = System.currentTimeMillis();
         System.out.println("Time taken to complete rebusgen : "+(et-st));
         if (theBestRebus != null) {
             if (theBestRebus.getLeft() != null && theBestRebus.getLeft().getRebus() != null && theBestRebus.getLeft().getRebus().length() > 0) {
                 System.out.println("Left : "+theBestRebus.getLeft().getRebus());
                 System.out.println("Recursion starts here");

                 theBestRebus.setLeft(rebusGen(theBestRebus.getLeft().getRebus()));
                 if (theBestRebus.getRight() != null && theBestRebus.getRight().getRebus() != null
                         && !"".equalsIgnoreCase(theBestRebus.getRight().getRebus()))
                 theBestRebus.setRight(new RebusNode(theBestRebus.getRight().getRebus()+theBestRebus.getLeft().getRight().getRebus(),0,null,null));
             }

         }
         return theBestRebus;
     }

     public void testRebusGen () {
         String word = "solve";
               long st = System.currentTimeMillis();

         RebusNode rebusnode = rebusGen(word);

//        System.out.println("Rebus Word for "+word+" : "+rebusnode.getRebus());
//                System.out.println("LeftAdd for "+word+" : "+rebusnode.getLeft().getRebus());
//                System.out.println("RightSub for "+word+" : "+rebusnode.getRight().getRebus());
        long et = System.currentTimeMillis();

             rebusnode.setRight(rebusGen(rebusnode.getRight().getRebus()));


         Utils.printRebus(rebusnode);
         System.out.println("Time taken to compute rebus : "+(et-st));


     }

     class CombinationComparator implements Comparator<CombinationBean> {
         public int compare(CombinationBean bean1,CombinationBean bean2) {
             return bean2.getCost() - bean1.getCost();
         }

     }
*/


}
